#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
// 链式二叉树结构体定义
typedef struct Bintree
{
	struct Bintree* left; // 左子节点指针
	struct Bintree* right; // 右子节点指针
	int val; // 节点值
}BT;
BT* BuyNode(int x);
BT* BuyTree();
void Pre_Order(BT* root);
void In_Order(BT* root);
void Post_Order(BT* root);
int TreeSize(BT* root);
int TreeDepth(BT* root);//Tree深度
int Tree_Ksize(BT* root, int k);//二叉树第k层节点个数
BT* TreeFind(BT* root, int x);
/**
 * 创建一个新的二叉树节点
 * @param x 节点值
 * @return 返回新创建的节点指针
 */
BT* BuyTree_Node(int x)
{
	BT* TreeNode = (BT*)malloc(sizeof(BT));
	if (TreeNode == NULL)
	{
		perror("malloc false");
		return NULL;
	}
	TreeNode->left = NULL;
	TreeNode->right = NULL;
	TreeNode->val = x;
	return TreeNode;
}

/**
 * 创建一棵示例二叉树
 * @return 返回根节点指针
 */
BT* BuyTree()
{
	BT* Treeenode1 = BuyTree_Node(1);
	BT* Treeenode2 = BuyTree_Node(2);
	BT* Treeenode3 = BuyTree_Node(3);
	BT* Treeenode4 = BuyTree_Node(4);
	BT* Treeenode5 = BuyTree_Node(5);
	BT* Treeenode6 = BuyTree_Node(6);
	Treeenode1->left = Treeenode2;
	Treeenode1->right = Treeenode4;
	Treeenode2->left = Treeenode3;
	Treeenode4->left = Treeenode5;
	Treeenode4->right = Treeenode6;
	return Treeenode1;
}

/**
 * 前序遍历二叉树
 * @param root 根节点指针
 */
void Pre_Order(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->val);
	Pre_Order(root->left);
	Pre_Order(root->right);
}
/**
 * 中序遍历二叉树
 * @param root 根节点指针
 */
void In_Order(BT* root)
{
	if( root == NULL)
	{
		printf("N ");
		return;
	}
	In_Order(root->left);
	printf("%d ", root->val);
	In_Order(root->right);
}

/**
 * 后序遍历二叉树
 * @param root 根节点指针
 */
void Post_Order(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	Post_Order(root->left);
	Post_Order(root->right);
	printf("%d ", root->val);
}

/**
 * 计算二叉树的节点数量
 * @param root 根节点指针
 * @return 返回二叉树的节点数量
 */
int Tree_Size(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return Tree_Size(root->left) + Tree_Size(root->right) + 1;
}

/**
 * 计算二叉树的最大深度
 * @param root 根节点指针
 * @return 返回二叉树的最大深度
 */
int Tree_Deepth(BT*root)
{
	if(root==NULL)
	{
		return 0;
	}
	int leftdepth = Tree_Deepth(root->left) + 1; // 递归计算左子树深度
	int rightdepth = Tree_Deepth(root->right) + 1; // 递归计算右子树深度
	return leftdepth > rightdepth ? leftdepth : rightdepth;
}
int Tree_Ksize(BT* root, int k)//二叉树第k层节点个数
{
    assert(k>=1);
    if(root==NULL)
    {
        return 0;
    }
    if(k==1)
    {
        return 1;
    }
    return Tree_Ksize(root->right,k-1)+ Tree_Ksize(root->left,k-1);
}

BT* TreeFind(BT* root, int x)//查找二叉树中的指定节点
{
	if(root==NULL)
	{
		return NULL;
	}
	if(root->val==x)
	{
		return root;
	}
	BT*tmp1 = TreeFind(root->left,x);
	if(tmp1)
	return tmp1;
	tmp1 = TreeFind(root->right,x);
	if(tmp1)
	return tmp1;

	return NULL;
}

int main()
{
	// 测试前序遍历
	/*Pre_Order(BuyTree());
	printf("\n");
	// 测试后序遍历
	Post_Order(BuyTree());
	// 计算并输出二叉树节点总数
	int sum = Tree_Size(BuyTree());
	printf("\n%d\n",sum);
	// 计算并输出二叉树的最大深度
	int depth = Tree_Deepth(BuyTree());
	printf("%d\n",depth);
    //计算并且输出二叉树第k层节点个数
    int sum1 = Tree_Ksize(BuyTree(),3);
    printf("%d\n",sum1);*/

	BT* tmp = TreeFind(BuyTree(),5);
	printf("%d\n",tmp->val);
	return 0;
}